File systems are usually cloned (e.g. taking snapshots) to provide, for example, crash-recovery capabilities. A common technique employed to maintain clones or snapshots of a file system using B-Tree (Balanced Tree) structures may be based on copy-on-write operations without a need to duplicate file system data shared by multiple clones. A live file system may be called a Logical Volume. The collection of all clones of a live file system and the live file system itself may be called a Logical Volume Family. Depending on which clones are created on which clone or live file system, the clones and the live file system within the Logical Volume Family forms a tree structure, which may be called the LVF Clone Tree. The live file system is always on the leaf of the tree. If a clone is created on another clone, one of the clone is the leaf, while the other clone is not the leaf of the tree. Existing implementations of copy-on-write operations may require a costly lookup to identify reference counts for tree structures in a file system.
For example, a file system may use a reference count table to keep track of how many references there are to each tree node, e.g. representing a group of consecutive allocation blocks or extents, in tree structures of the file system. It is not uncommon for a block on disk to have hundreds of references. Typically, whether to perform copy-on-write operations for a tree node associated with blocks of data in a file system may depend on a reference count of the tree node, which may indicate how many references to the tree node currently existing in the file system.
However, B-Tree structures in a file system tend to have huge fan out. The number of links between the first and second levels in a B-Tree structure can be, for example, in the hundreds. Thus, a reference count table storing reference counts for such B-Tree structures can be too large to fit in memory. Accessing the reference count table can result in wasting system resources with frequent memory paging operations. Additionally, traversing such a large sized table to locate a reference count for a tree node may take significant amount of time to complete and have a negative impact on the performance of a file system.
Therefore, current implementations of file systems requiring reference count checking do not optimize copy-on-write strategies to share data among clones and/or live versions of the file systems.